package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-12-02 20:10:12	 当前时间
 */
//给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。 
//
// 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层
//为第 h 层，则该层包含 1~ 2h 个节点。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,2,3,4,5,6]
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：root = [1]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目范围是[0, 5 * 104] 
// 0 <= Node.val <= 5 * 104 
// 题目数据保证输入的树是 完全二叉树 
// 
//
// 
//
// 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？ 
// Related Topics 树 深度优先搜索 二分查找 二叉树 
// 👍 827 👎 0

public class 完全二叉树的节点个数{
	public static void main(String[] args) {
		Solution solution = new 完全二叉树的节点个数().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {


	/**  解法参考：https://leetcode.cn/problems/count-complete-tree-nodes/solution/by-xiaochengtongxue_-guv3/
	 * 利用完全二叉树的性质：
	 *  1.定义：最后一层叶子节点 集中在最左边（依次从左到右分布。）
	 *  2. 除最后一层，其余上层为满二叉树。
	 *  怎么判断是否为满二叉树：
	 *  法一：
	 *  	1. 左子树的高度：l 、 右子树的高度：r
	 *      2. 若l==r 则是满二叉树（此时，左子树定为满二叉树）如 例子3、4。
	 *      		return 2^(l)-1 + 正常递归遍历右子树的个数 + 1
	 *       	否则 右子树为满二叉树 如 例子 1、2
	 *       		return 正常递归遍历左子树的个数 + 2^(r)-1 +1.
	 * 例子    1：         2:        3:           4:
	 *            1           1         1           1
	 *           / \         / \       / \         / \
	 *          2  3        2  3      2  3        2  3
	 *         /           /\        /\  /       /\  /\
	 *        4           4 5       4 5 6       4 5 6 7
	 *  法二：1. 一直遍历左节点的高度：l 、 一直遍历右节点的高度：r
	 *      若 l==r 则此时 整棵树为满二叉树。 如 例子4
	 *      	return 2^(l)-1
	 *      否则 按照普通递归方法计算
	 *  位运算：
	 *  	正数：左移n位 == 乘以2的n次方
	 *  	     右移n位 == 除以2的n次方
	 */
	public int countNodes(TreeNode root) {
		if (root==null) {
			return 0;
		}
		int lh = getHight(root.left);
		int rh = getHight(root.right);
		if (lh==rh){
			return  (1<<lh)+countNodes(root.right);
//			return (int) (Math.pow(2,lh) +countNodes(root.right));
		}else{
			return  (1<<rh)+countNodes(root.left);
//			return (int) (Math.pow(2,rh)+countNodes(root.left));
		}
	}

	private int getHight(TreeNode node) {
		int count = 0;
		while (node!=null){
			// 因为完全二叉树是基于左节点的 所以我们可以遍历到最深的左节点 此时的height就是树高
			node = node.left;
			count++;
		}
		return count;
	}


	/**
	 * 法二：1. 一直遍历左节点的高度：l 、 一直遍历右节点的高度：r
	 *      若 l==r 则此时 整棵树为满二叉树。 如 例子4
	 *      	return 2^(l)-1
	 *      否则 按照普通递归方法计算
	 */
	public int countNodes3(TreeNode root) {
		if (root==null){
			return 0;
		}
		TreeNode left = root.left;
		TreeNode right = root.right;
		int lh = 0, rh = 0;
		while (left!=null){
			left = left.left;
			lh++;
		}
		while (right!=null){
			right = right.right;
			rh++;
		}
		if (lh==rh){
//			说明整棵树是满二叉树   lh此时只是左子树的深度
//			return (int) (Math.pow(2,lh+1)-1);
			return  (2<<lh)-1;
//	        8421
//			3210
//			← 1
		}else{
//			按照正常情况递归计算
			return countNodes(root.left)+countNodes(root.right)+1;
		}

	}


	// 普通解法
	public int countNodes2(TreeNode root) {
		if (root==null) return 0;

		int left = countNodes(root.left);
		int right = countNodes(root.right);

		return left+right+1;
	}

	/** 普通非递归解法：
	 * 	先序遍历
	 * 中左右
	 *
	 * | 3 2
	 *  1
	 */
    public int countNodes1(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
//		ArrayList<Integer> list = new ArrayList<>();
		int len = 0;
		if (root!=null){
			stack.push(root);
			while (!stack.isEmpty()){
				TreeNode node = stack.pop();
//				list.add(node.val);
				len++;
				if (node.right!=null){
					stack.push(node.right);
				}
				if (node.left!=null){
					stack.push(node.left);
				}
			}
		}
//		return list.size();
		return len;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
